{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Closest Binary Search Tree Value II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #stack #tree #depth-first-search #binary-search-tree #two-pointers #binary-tree #heap-priority-queue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #栈 #树 #深度优先搜索 #二叉搜索树 #双指针 #二叉树 #堆（优先队列）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: closestKValues"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最接近的二叉搜索树值 II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定二叉搜索树的根&nbsp;<code>root</code>&nbsp;、一个目标值&nbsp;<code>target</code>&nbsp;和一个整数&nbsp;<code>k</code>&nbsp;，返回BST中最接近目标的 <code>k</code> 个值。你可以按 <strong>任意顺序</strong> 返回答案。</p>\n",
    "\n",
    "<p>题目&nbsp;<strong>保证</strong>&nbsp;该二叉搜索树中只会存在一种&nbsp;k 个值集合最接近&nbsp;<code>target</code></p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img src=\"https://assets.leetcode.com/uploads/2021/03/12/closest1-1-tree.jpg\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> root = [4,2,5,1,3]，目标值 = 3.714286，且 <em>k</em> = 2\n",
    "<strong>输出:</strong> [4,3]</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> root = [1], target = 0.000000, k = 1\n",
    "<strong>输出:</strong> [1]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>二叉树的节点总数为&nbsp;<code>n</code></li>\n",
    "\t<li><code>1 &lt;= k &lt;= n &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li><code>0 &lt;= Node.val &lt;= 10<sup>9</sup></code></li>\n",
    "\t<li><code>-10<sup>9</sup>&nbsp;&lt;= target &lt;= 10<sup>9</sup></code></li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>进阶：</strong>假设该二叉搜索树是平衡的，请问您是否能在小于&nbsp;<code>O(n)</code>（&nbsp;<code>n = total nodes</code>&nbsp;）的时间复杂度内解决该问题呢？</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [closest-binary-search-tree-value-ii](https://leetcode.cn/problems/closest-binary-search-tree-value-ii/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [closest-binary-search-tree-value-ii](https://leetcode.cn/problems/closest-binary-search-tree-value-ii/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[4,2,5,1,3]\\n3.714286\\n2', '[1]\\n0.000000\\n1']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def closestKValues(self, root: Optional[TreeNode], target: float, k: int) -> List[int]:\n",
    "        hp = []\n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return\n",
    "            diff = abs(node.val - target)\n",
    "            if len(hp) < k or - diff > hp[0][0]:\n",
    "                heapq.heappush(hp, [-diff, node.val])\n",
    "                if len(hp) > k:\n",
    "                    heapq.heappop(hp)\n",
    "                dfs(node.left)\n",
    "                dfs(node.right)\n",
    "            else:\n",
    "                if node.val < target:\n",
    "                    dfs(node.right)\n",
    "                else:\n",
    "                    dfs(node.left)\n",
    "        dfs(root)\n",
    "        return [x[1] for x in hp]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def closestKValues(self, root: Optional[TreeNode], target: float, k: int) -> List[int]:\n",
    "        res = []\n",
    "        def dfs(node):\n",
    "            nonlocal res\n",
    "            if not node:\n",
    "                return\n",
    "            dfs(node.left)\n",
    "            if len(res) < k:\n",
    "                res = [node.val] + res\n",
    "            elif abs(res[-1] - target) > abs(node.val - target):\n",
    "                res.pop()\n",
    "                res = [node.val] + res\n",
    "            else:\n",
    "                return\n",
    "            dfs(node.right)\n",
    "        \n",
    "        dfs(root)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "from bisect import bisect_left\n",
    "class Solution:\n",
    "    def closestKValues(self, root: Optional[TreeNode], target: float, k: int) -> List[int]:\n",
    "        arr = []\n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return\n",
    "            dfs(root.left)\n",
    "            arr.append(root.val)\n",
    "            dfs(root.right)\n",
    "        dfs(root)\n",
    "        res = []\n",
    "        right = bisect.bisect_left(arr, target)\n",
    "        left = right - 1\n",
    "        n = len(arr)\n",
    "        while len(res) < k:\n",
    "            if left >= 0 and right <= n - 1:\n",
    "                if abs(arr[left] - target) < abs(arr[right] - target):\n",
    "                    res.append(arr[left])\n",
    "                    left -= 1\n",
    "                else:\n",
    "                    res.append(arr[right])\n",
    "                    right += 1\n",
    "            elif left >= 0:\n",
    "                res.append(arr[left])\n",
    "                left -= 1\n",
    "            else:\n",
    "                res.append(arr[right])\n",
    "                right += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def closestKValues(self, root: Optional[TreeNode], target: float, k: int) -> List[int]:\n",
    "        ans = []\n",
    "        arr = []\n",
    "        def dfs(root):\n",
    "            if root is None:\n",
    "                return \n",
    "            dfs(root.left)\n",
    "            arr.append(root.val)\n",
    "            dfs(root.right)\n",
    "        dfs(root)\n",
    "        right = bisect_left(arr, target)\n",
    "        left = right - 1\n",
    "        for i in range(k):\n",
    "            if left >= 0 and right < len(arr):\n",
    "                if abs(arr[left] - target) <= abs(arr[right] - target):\n",
    "                    ans.append(arr[left])\n",
    "                    left -= 1\n",
    "                else:\n",
    "                    ans.append(arr[right])\n",
    "                    right += 1\n",
    "            elif left >= 0:\n",
    "                ans.append(arr[left])\n",
    "                left -= 1\n",
    "            else:\n",
    "                ans.append(arr[right])\n",
    "                right += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def dfs(self, node: TreeNode, target: float, k: int) -> None:\n",
    "        if node == None:\n",
    "            return \n",
    "        diff = abs(node.val - target)\n",
    "        if len(self.max_heap) < k:              #最大堆可以容纳k个\n",
    "            heapq.heappush(self.max_heap, (-diff, node.val))        #node会报错 Python会说TreeNode无法比较\n",
    "        else:\n",
    "            if diff < self.max_heap[0][0] * (-1): #让差距更小的进堆\n",
    "                heapq.heappop(self.max_heap)\n",
    "                heapq.heappush(self.max_heap, (-diff, node.val))\n",
    "        self.dfs(node.left, target, k)          #递归左子\n",
    "        self.dfs(node.right, target, k)         #递归右子\n",
    "\n",
    "    def closestKValues(self, root: TreeNode, target: float, k: int) -> List[int]:\n",
    "        self.max_heap = []\n",
    "        self.dfs(root, target, k)\n",
    "        res = []\n",
    "        for diff, node_val in self.max_heap:\n",
    "            res.append(node_val)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def closestKValues(self, root: Optional[TreeNode], target: float, k: int) -> List[int]:\n",
    "        # 中序遍历 + 堆栈 + 不用进行空判断\n",
    "        stack, res = [], []\n",
    "        while stack or root:\n",
    "            while root:\n",
    "                stack.append(root)\n",
    "                root = root.left\n",
    "            root = stack.pop()\n",
    "            if len(res) < k:\n",
    "                res.append(root.val)\n",
    "            elif abs(res[0] - target) > abs(root.val - target):\n",
    "                res.pop(0)\n",
    "                res.append(root.val)\n",
    "            else:\n",
    "                break\n",
    "            root = root.right\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "from collections import deque\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def closestKValues(self, root: Optional[TreeNode], target: float, k: int) -> List[int]:\n",
    "        knn = deque()\n",
    "        def findKNN(root, target, k):\n",
    "            nonlocal knn\n",
    "            if not root:\n",
    "                return \n",
    "            # In-order traversal\n",
    "            findKNN(root.left, target, k)\n",
    "            if len(knn) < k:\n",
    "                # to ensure the largest being placed at the top\n",
    "                knn.append(root.val)\n",
    "            else:\n",
    "                smallest = knn.popleft()\n",
    "                if abs(smallest - target) < abs(root.val - target):\n",
    "                    knn.appendleft(smallest)\n",
    "                    return list(knn)\n",
    "                else:\n",
    "                    knn.append(root.val)\n",
    "            findKNN(root.right, target, k)\n",
    "        findKNN(root, target, k)\n",
    "        return list(knn)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def closestKValues(self, root: Optional[TreeNode], target: float, k: int) -> List[int]:\n",
    "        nums = []\n",
    "\n",
    "        def traverse(node):\n",
    "            if not node:\n",
    "                return\n",
    "            traverse(node.left)\n",
    "            nums.append(node.val)\n",
    "            traverse(node.right)\n",
    "        \n",
    "        traverse(root)\n",
    "\n",
    "        left, right = 0, len(nums)-1\n",
    "        while left < right:\n",
    "            mid = (left + right) // 2\n",
    "            # if nums[mid] == target:\n",
    "            #     break\n",
    "            if nums[mid] < target:\n",
    "                left = mid+1\n",
    "            else:\n",
    "                right = mid\n",
    "        left = right - 1\n",
    "        ans = []\n",
    "        for i in range(k):\n",
    "            if left >= 0 and right < len(nums):\n",
    "                if abs(nums[left] - target) < abs(nums[right] - target):\n",
    "                    ans.append(nums[left])\n",
    "                    left -= 1\n",
    "                else:\n",
    "                    ans.append(nums[right])\n",
    "                    right += 1\n",
    "            elif left >= 0:\n",
    "                ans.append(nums[left])\n",
    "                left -= 1\n",
    "            else:\n",
    "                ans.append(nums[right])\n",
    "                right += 1\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def closestKValues(self, root: Optional[TreeNode], target: float, k: int) -> List[int]:\n",
    "        smaller_stack, larger_stack = [], []\n",
    "\n",
    "        while root:\n",
    "            if root.val <= target:\n",
    "                smaller_stack.append(root)\n",
    "                root = root.right\n",
    "            else:\n",
    "                larger_stack.append(root)\n",
    "                root = root.left\n",
    "\n",
    "        result = []\n",
    "\n",
    "        for index in range(k):\n",
    "            left_diff = float(\"inf\") if not smaller_stack else target - smaller_stack[-1].val\n",
    "            right_diff = float(\"inf\") if not larger_stack else larger_stack[-1].val - target\n",
    "\n",
    "            if left_diff <= right_diff:\n",
    "                node = smaller_stack.pop()\n",
    "                result.append(node.val)\n",
    "                node = node.left\n",
    "                while node:\n",
    "                    smaller_stack.append(node)\n",
    "                    node = node.right\n",
    "            else:\n",
    "                node = larger_stack.pop()\n",
    "                result.append(node.val)\n",
    "                node = node.right\n",
    "                while node:\n",
    "                    larger_stack.append(node)\n",
    "                    node = node.left\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def closestKValues(self, root: Optional[TreeNode], target: float, k: int) -> List[int]:\n",
    "        values =[]\n",
    "        res =[]\n",
    "\n",
    "        def dfs(root):\n",
    "            if root is None:\n",
    "                return\n",
    "            \n",
    "            dfs(root.left)\n",
    "            values.append(root.val)\n",
    "            dfs(root.right)\n",
    "        \n",
    "        dfs(root)\n",
    "        right = bisect_left(values,target)\n",
    "        left = right-1\n",
    "\n",
    "        for _ in range(k):\n",
    "            if left >=0 and right <len(values):\n",
    "                if (target-values[left]) >= (values[right]-target):\n",
    "                    res.append(values[right])\n",
    "                    right+=1\n",
    "                else:\n",
    "                    res.append(values[left])\n",
    "                    left -=1\n",
    "                \n",
    "            elif left <0:\n",
    "                res.append(values[right])\n",
    "                right +=1\n",
    "            else:\n",
    "                res.append(values[left])\n",
    "                left -=1\n",
    "        \n",
    "        return res\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def closestKValues(self, root: Optional[TreeNode], target: float, k: int) -> List[int]:\n",
    "        knn = []\n",
    "        def findKNN(root, target, k):\n",
    "            nonlocal knn\n",
    "            if not root:\n",
    "                return \n",
    "            key = abs(root.val - target)\n",
    "            if len(knn) < k:\n",
    "                # to ensure the largest being placed at the top\n",
    "                heapq.heappush(knn, (-key, root.val))\n",
    "            else:\n",
    "                heapq.heappushpop(knn, (-key, root.val))\n",
    "            findKNN(root.left, target, k)\n",
    "            findKNN(root.right, target, k)\n",
    "        findKNN(root, target, k)\n",
    "        return [i[1] for i in knn]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def closestKValues(self, root: Optional[TreeNode], target: float, k: int) -> List[int]:\n",
    "        if not root:\n",
    "            return\n",
    "        res = []\n",
    "        stack = [(root, 0)]\n",
    "        while stack:\n",
    "            node, status = stack.pop()\n",
    "            if not node:\n",
    "                continue\n",
    "            if status == 0:\n",
    "                stack.append((node.right, 0))\n",
    "                stack.append((node, 1))\n",
    "                stack.append((node.left, 0))\n",
    "            elif status == 1:\n",
    "                if k > len(res):\n",
    "                    res.append(node.val)\n",
    "                elif abs(res[0] - target) > abs(node.val - target):\n",
    "                    res.pop(0)\n",
    "                    res.append(node.val)\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def closestKValues(self, root: TreeNode, target: float, k: int) -> List[int]:\n",
    "            # 解法3:非递归方法\n",
    "            if not root:\n",
    "                return\n",
    "            DONE = 1 # 已读结点\n",
    "            UNDO = 0 # 未读结点\n",
    "            res = []\n",
    "            stack = [(root, UNDO)]\n",
    "            while stack:\n",
    "                node, status = stack.pop()\n",
    "                if not node:\n",
    "                    continue\n",
    "                if status == UNDO:\n",
    "                    stack.append((node.right, UNDO))\n",
    "                    stack.append((node, DONE))\n",
    "                    stack.append((node.left, UNDO))\n",
    "                elif status == DONE:\n",
    "                    if k > len(res):\n",
    "                        res.append(node.val)\n",
    "                    elif abs(res[0] - target) > abs(node.val - target):\n",
    "                        res.pop(0)\n",
    "                        res.append(node.val)\n",
    "            return res   "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def closestKValues(self, root: Optional[TreeNode], target: float, k: int) -> List[int]:\n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return []\n",
    "            return dfs(root.left) + [root.val] + dfs(root.right)\n",
    "        \n",
    "        array = dfs(root)\n",
    "        res = []\n",
    "        j = bisect_left(array, target)\n",
    "        i = j - 1 \n",
    "        for _ in range(k):\n",
    "            if i >= 0 and j < len(array):\n",
    "                if abs(array[i]-target) <= abs(array[j]-target):\n",
    "                    res.append(array[i])\n",
    "                    i -= 1\n",
    "                else:\n",
    "                    res.append(array[j])\n",
    "                    j += 1\n",
    "            elif i >= 0:\n",
    "                res.append(array[i])\n",
    "                i -= 1\n",
    "            else:\n",
    "                res.append(array[j])\n",
    "                j += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def closestKValues(self, root: Optional[TreeNode], target: float, k: int) -> List[int]:\n",
    "        res = []\n",
    "        def dfs(root):\n",
    "            if not root: return\n",
    "            dfs(root.left)\n",
    "            res.append(root.val)\n",
    "            dfs(root.right)\n",
    "        dfs(root)\n",
    "        ans = []\n",
    "        while len(ans) < k:\n",
    "            j = 0\n",
    "            mn = inf\n",
    "            for i in range(len(res)):\n",
    "                if abs(res[i] - target) < mn:\n",
    "                    mn = abs(res[i] - target)\n",
    "                    j = i \n",
    "            ans.append(res[j])\n",
    "            res[j] = inf\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def closestKValues(self, root: Optional[TreeNode], target: float, k: int) -> List[int]:\n",
    "        # 维护一个队列，双端的，不断调整就行了\n",
    "        # 1. quit at left k \n",
    "        # 2. quit at right more than left k \n",
    "        # [1,2,3,4,5]  if closer then append,and remove ,else stop and return \n",
    "\n",
    "        klist = []\n",
    "\n",
    "        def dfs(node):\n",
    "            if not node:return \n",
    "            dfs(node.left)\n",
    "            if len(klist) == 0:\n",
    "                klist.append(node.val)\n",
    "            elif len(klist) >= k:\n",
    "                if abs(node.val - target) < abs(klist[0] - target):\n",
    "                    klist.append(node.val)\n",
    "                    klist.pop(0)\n",
    "                else:\n",
    "                    return \n",
    "            else:\n",
    "                klist.append(node.val)\n",
    "            dfs(node.right)\n",
    "\n",
    "        dfs(root)\n",
    "        return klist\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def closestKValues(self, root: Optional[TreeNode], target: float, k: int) -> List[int]:\n",
    "        nums = []\n",
    "        def dfs(root):\n",
    "            if not root: return\n",
    "            dfs(root.left)\n",
    "            nums.append(root.val)\n",
    "            dfs(root.right)\n",
    "        \n",
    "        dfs(root)\n",
    "        right = self.find_upper_closest(nums, target)\n",
    "        left = right - 1\n",
    "        for _ in range(k):\n",
    "            if left < 0:\n",
    "                right += 1\n",
    "            elif right >= len(nums) or target - nums[left] <= nums[right] - target:\n",
    "                left -= 1\n",
    "            else:\n",
    "                right += 1\n",
    "        \n",
    "        return nums[left + 1: right]\n",
    "\n",
    "    \n",
    "    def find_upper_closest(self, nums, target):\n",
    "        left, right = 0, len(nums) - 1\n",
    "        while left + 1 < right:\n",
    "            mid = (left + right) // 2\n",
    "            if nums[mid] < target:\n",
    "                left = mid\n",
    "            else:\n",
    "                right = mid\n",
    "        \n",
    "        if nums[left] >= target:\n",
    "            return left\n",
    "        if nums[right] >= target:\n",
    "            return right\n",
    "        return len(nums)\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def closestKValues(self, root: Optional[TreeNode], target: float, k: int) -> List[int]:\n",
    "        ans = []\n",
    "        def dfs(node: Optional[TreeNode]):\n",
    "            if not node:\n",
    "                return\n",
    "            dfs(node.left)\n",
    "            if len(ans) < k:\n",
    "                ans.append(node.val)\n",
    "            else:\n",
    "                if abs(node.val - target) < abs(ans[0] - target):\n",
    "                    ans.pop(0)\n",
    "                    ans.append(node.val)\n",
    "                else:\n",
    "                    return \n",
    "            dfs(node.right)\n",
    "        dfs(root)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def closestKValues(self, root: Optional[TreeNode], target: float, k: int) -> List[int]:\n",
    "        q = collections.deque()\n",
    "\n",
    "        def inorder(root):\n",
    "            if root is None:\n",
    "                return\n",
    "            inorder(root.left)\n",
    "            if len(q) < k:\n",
    "                q.append(root.val)\n",
    "            elif root.val < target or abs(q[0] - target) > root.val - target:\n",
    "                q.popleft()\n",
    "                q.append(root.val)\n",
    "            \n",
    "            # 剪枝\n",
    "            if len(q) < k or q[0] <= target:\n",
    "                inorder(root.right)\n",
    "\n",
    "        inorder(root)\n",
    "        \n",
    "        return list(q)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def closestKValues(self, root: Optional[TreeNode], target: float, k: int) -> List[int]:\n",
    "        self.lst = []\n",
    "        self.inOrder(root)\n",
    "        n = len(self.lst)\n",
    "        idx = self.binSearch(target)\n",
    "        ans = []\n",
    "        i, j = idx, idx + 1\n",
    "        if i < 0:\n",
    "            ans.extend(self.lst[0: k])\n",
    "        elif j == n:\n",
    "            ans.extend(self.lst[-1: -k - 1: -1])\n",
    "        else:\n",
    "            for x in range(k):\n",
    "                if target - self.lst[i] < self.lst[j] - target:\n",
    "                    ans.append(self.lst[i])\n",
    "                    if i == 0:\n",
    "                        ans.extend(self.lst[j: j + k - x - 1])\n",
    "                        break\n",
    "                    i -= 1\n",
    "                else:\n",
    "                    ans.append(self.lst[j])\n",
    "                    if j == n - 1:\n",
    "                        ans.extend(self.lst[i: i - k + x + 1: -1])\n",
    "                        break\n",
    "                    j += 1\n",
    "        return ans\n",
    "\n",
    "    def binSearch(self, target):\n",
    "        i, j = 0, len(self.lst) - 1\n",
    "        while i <= j:\n",
    "            m = (i + j) // 2\n",
    "            if self.lst[m] > target:\n",
    "                j = m - 1\n",
    "            else:\n",
    "                i = m + 1\n",
    "        return j\n",
    "    \n",
    "    def inOrder(self, root):\n",
    "        if root == None:\n",
    "            return\n",
    "        self.inOrder(root.left)\n",
    "        self.lst.append(root.val)\n",
    "        self.inOrder(root.right)\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def closestKValues(self, root: Optional[TreeNode], target: float, k: int) -> List[int]:\n",
    "        res = []\n",
    "        stack = []\n",
    "        DONE = 1\n",
    "        UNDO = 0\n",
    "        stack.append((root,UNDO))\n",
    "        while stack:\n",
    "            node, statu = stack.pop()\n",
    "            if not node:\n",
    "                continue\n",
    "            if statu == UNDO:\n",
    "                stack.append((node.right,UNDO))\n",
    "                stack.append((node,DONE))\n",
    "                stack.append((node.left,UNDO))\n",
    "            else:\n",
    "                if len(res) < k:\n",
    "                    res.append(node.val)\n",
    "                elif abs(res[0] - target) > abs(node.val - target):\n",
    "                    res.append(node.val)\n",
    "                    res.pop(0)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def closestKValues(self, root: Optional[TreeNode], target: float, k: int) -> List[int]:\n",
    "        ans  = []\n",
    "        arr = []\n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return \n",
    "            dfs(root.left)\n",
    "            arr.append(root.val)\n",
    "            dfs(root.right)\n",
    "        dfs(root)   \n",
    "        right = bisect_left(arr,target)\n",
    "        left = right - 1\n",
    "        for i in range(k):\n",
    "            if left >= 0 and right < len(arr):\n",
    "                if abs(arr[left] - target) <= abs(arr[right] - target):\n",
    "                    ans.append(arr[left])\n",
    "                    left -= 1\n",
    "                else:\n",
    "                    ans.append(arr[right])\n",
    "                    right += 1\n",
    "            elif left >= 0:\n",
    "                ans.append(arr[left])\n",
    "                left -= 1\n",
    "            else:\n",
    "                ans.append(arr[right])\n",
    "                right += 1\n",
    "        return ans\n",
    "        # ans = []\n",
    "        # arr = []\n",
    "        # def dfs(root):# 中序遍历\n",
    "        #     if root is None:\n",
    "        #         return\n",
    "        #     dfs(root.left)\n",
    "        #     arr.append(root.val)\n",
    "        #     dfs(root.right)\n",
    "        # dfs(root)# 中序遍历获取的是搜索树的排序结果\n",
    "        # right = bisect_left(arr, target)\n",
    "        # left = right - 1\n",
    "        # for i in range(k):# 双指针\n",
    "        #     if left>=0 and right < len(arr):\n",
    "        #         if abs(arr[left] - target) <= abs(arr[right] - target):\n",
    "        #             ans.append(arr[left])\n",
    "        #             left -= 1\n",
    "        #         else:\n",
    "        #             ans.append(arr[right])\n",
    "        #             right += 1\n",
    "        #     elif left>=0:\n",
    "        #         ans.append(arr[left])\n",
    "        #         left -= 1\n",
    "        #     else:\n",
    "        #         ans.append(arr[right])\n",
    "        #         right += 1\n",
    "        # return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def closestKValues(self, root: Optional[TreeNode], target: float, k: int) -> List[int]:\n",
    "        res = []\n",
    "        def dfs(root):\n",
    "            if not root: return\n",
    "            dfs(root.left)\n",
    "            res.append(root.val)\n",
    "            dfs(root.right)\n",
    "        dfs(root)\n",
    "        ans = []\n",
    "        while len(ans) < k:\n",
    "            j = 0\n",
    "            mn = inf\n",
    "            for i in range(len(res)):\n",
    "                if res[i] == inf: continue\n",
    "                if abs(res[i] - target) < mn:\n",
    "                    mn = abs(res[i] - target)\n",
    "                    j = i \n",
    "                else:\n",
    "                    break\n",
    "            ans.append(res[j])\n",
    "            res[j] = inf\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    # def left_bound(self, arr,target):\n",
    "    #     left, right = 0, len(arr) - 1\n",
    "    #     while left <= right:\n",
    "    #         mid = left + (right - left) // 2\n",
    "    #         if arr[mid] < target:\n",
    "    #             right = mid - 1\n",
    "    #         elif arr[mid] > target:\n",
    "    #             left = mid + 1\n",
    "    #         else: # arr[mid] > target:\n",
    "    #             right = mid - 1\n",
    "    #     if left >= len(arr):\n",
    "    #         return -1\n",
    "    #     return left\n",
    "\n",
    "\n",
    "    def left_bound(self, arr, target):\n",
    "        left, right = 0, len(arr)\n",
    "        while left < right:\n",
    "            mid = (left + right) // 2\n",
    "            if arr[mid] < target:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid\n",
    "        return left\n",
    "\n",
    "    def closestKValues(self, root: Optional[TreeNode], target: float, k: int) -> List[int]:\n",
    "        ans = []\n",
    "        arr = []\n",
    "        def dfs(root):\n",
    "            if root == None:\n",
    "                return\n",
    "            dfs(root.left)\n",
    "            arr.append(root.val)\n",
    "            dfs(root.right)\n",
    "        dfs(root)\n",
    "        right = self.left_bound(arr,target)\n",
    "        left = right - 1\n",
    "        for i in range(k):\n",
    "            if left >= 0 and right < len(arr):\n",
    "                if abs(arr[left] - target) <= abs(arr[right] - target):\n",
    "                    ans.append(arr[left])\n",
    "                    left -= 1\n",
    "                else:\n",
    "                    ans.append(arr[right])\n",
    "                    right += 1\n",
    "            elif left >= 0:\n",
    "                ans.append(arr[left])\n",
    "                left -= 1\n",
    "            else:\n",
    "                ans.append(arr[right])\n",
    "                right += 1     \n",
    "        return ans             \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def closestKValues(self, root: Optional[TreeNode], target: float, k: int) -> List[int]:\n",
    "        \n",
    "        from collections import deque\n",
    "        queue = deque()\n",
    "\n",
    "        self._traverse(root, target, queue, k)\n",
    "        return list(queue)\n",
    "\n",
    "    \n",
    "    def _traverse(self, root, target, queue, k):\n",
    "        if root is None:\n",
    "            return\n",
    "        \n",
    "        # inorder\n",
    "        self._traverse(root.left, target, queue, k)\n",
    "\n",
    "        if len(queue) < k:\n",
    "            queue.append(root.val)\n",
    "        else:\n",
    "            head = queue[0]\n",
    "            if abs(root.val - target) < abs(head - target):\n",
    "                queue.append(root.val)\n",
    "                queue.popleft()\n",
    "\n",
    "\n",
    "        self._traverse(root.right, target, queue, k)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def closestKValues(self, root: Optional[TreeNode], target: float, k: int) -> List[int]:\n",
    "        q = collections.deque()\n",
    "\n",
    "        def inorder(root):\n",
    "            if root is None:\n",
    "                return\n",
    "            inorder(root.left)\n",
    "            if len(q) < k:\n",
    "                q.append(root.val)\n",
    "                inorder(root.right)\n",
    "                return\n",
    "            \n",
    "            if root.val < target or abs(q[0] - target) > root.val - target:\n",
    "                q.popleft()\n",
    "                q.append(root.val)\n",
    "            \n",
    "            # 剪枝\n",
    "            if q[0] <= target:\n",
    "                inorder(root.right)\n",
    "\n",
    "        inorder(root)\n",
    "        \n",
    "        return list(q)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def closestKValues(self, root: Optional[TreeNode], target: float, k: int) -> List[int]:\n",
    "        def move_upper():\n",
    "            if upper:\n",
    "                last = upper.pop()\n",
    "                last = last.right \n",
    "                while last:\n",
    "                    upper.append(last)\n",
    "                    last = last.left \n",
    "        def move_lower():\n",
    "            if lower:\n",
    "                last = lower.pop()\n",
    "                last = last.left \n",
    "                while last:\n",
    "                    lower.append(last)\n",
    "                    last = last.right \n",
    "        upper = []\n",
    "        cur = root \n",
    "        while cur:\n",
    "            upper.append(cur)\n",
    "            cur = cur.left \n",
    "        lower = []\n",
    "        cur = root \n",
    "        while cur:\n",
    "            lower.append(cur)\n",
    "            cur = cur.right \n",
    "        while upper and upper[-1].val < target:\n",
    "            move_upper()\n",
    "        while lower and lower[-1].val >= target:\n",
    "            move_lower()\n",
    "        res = []\n",
    "        for _ in range(k):\n",
    "            l = lower[-1].val if lower else - float('inf')\n",
    "            u = upper[-1].val if upper else float('inf')\n",
    "            if u - target <= target - l:\n",
    "                res.append(u)\n",
    "                move_upper()\n",
    "            else:\n",
    "                res.append(l)\n",
    "                move_lower()\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution(object):\n",
    "    def closestKValues(self, root, target, k):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :type target: float\n",
    "        :type k: int\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        ret = []\n",
    "        succ = []\n",
    "        pred = []\n",
    "        \n",
    "        self.initializePredecessorStack(root, target, pred)\n",
    "        self.initializeSuccessorStack(root, target, succ)\n",
    "        \n",
    "        if succ and pred and succ[-1].val == pred[-1].val:\n",
    "            self.getNextPredecessor(pred)\n",
    "\n",
    "        while k > 0:\n",
    "            if not succ:\n",
    "                ret.append(self.getNextPredecessor(pred))\n",
    "            elif not pred:\n",
    "                ret.append(self.getNextSuccessor(succ))\n",
    "            else:\n",
    "                succ_diff = abs(succ[-1].val - target)\n",
    "                pred_diff = abs(pred[-1].val - target)\n",
    "                \n",
    "                if succ_diff < pred_diff :\n",
    "                    ret.append(self.getNextSuccessor(succ))\n",
    "                else:\n",
    "                    ret.append(self.getNextPredecessor(pred))\n",
    "                    \n",
    "            k -= 1\n",
    "            \n",
    "        return ret\n",
    "    \n",
    "    def initializeSuccessorStack(self, root, target, succ):\n",
    "        while root:\n",
    "            if root.val == target:\n",
    "                succ.append(root)\n",
    "                break\n",
    "            elif root.val > target:\n",
    "                succ.append(root)\n",
    "                root = root.left\n",
    "            else:\n",
    "                root = root.right\n",
    "\n",
    "    def initializePredecessorStack(self, root, target, pred):\n",
    "        while root: \n",
    "            if root.val == target:\n",
    "                pred.append(root)\n",
    "                break\n",
    "            elif root.val < target:\n",
    "                pred.append(root)\n",
    "                root = root.right\n",
    "            else:\n",
    "                root = root.left\n",
    "                \n",
    "    def getNextSuccessor(self, succ):\n",
    "        curr = succ.pop()\n",
    "        ret = curr.val\n",
    "        curr = curr.right\n",
    "        while curr:\n",
    "            succ.append(curr)\n",
    "            curr = curr.left\n",
    "        return ret\n",
    "\n",
    "    def getNextPredecessor(self, pred):\n",
    "        curr = pred.pop()\n",
    "        ret = curr.val\n",
    "        curr = curr.left\n",
    "        while curr:\n",
    "            pred.append(curr)\n",
    "            curr = curr.right\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def closestKValues(self, root: Optional[TreeNode], target: float, k: int) -> List[int]:\n",
    "        #最小堆处理+dfs遍历即可\n",
    "        h=[]\n",
    "        def dfs(x):\n",
    "            if x:\n",
    "                cur=x.val\n",
    "                d=abs(cur-target)\n",
    "                if len(h)<k:\n",
    "                    heapq.heappush(h,(-d,cur))\n",
    "                else:\n",
    "                    if d<-h[0][0]:\n",
    "                        heapq.heapreplace(h,(-d,cur))\n",
    "                dfs(x.left)\n",
    "                dfs(x.right)\n",
    "        dfs(root)\n",
    "        return [v[1] for v in h]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def closestKValues(self, root: Optional[TreeNode], target: float, k: int) -> List[int]:\n",
    "        def move_upper():\n",
    "            if upper:\n",
    "                last = upper.pop()\n",
    "                last = last.right \n",
    "                while last:\n",
    "                    upper.append(last)\n",
    "                    last = last.left \n",
    "        def move_lower():\n",
    "            if lower:\n",
    "                last = lower.pop()\n",
    "                last = last.left \n",
    "                while last:\n",
    "                    lower.append(last)\n",
    "                    last = last.right \n",
    "        upper = []\n",
    "        cur = root \n",
    "        while cur:\n",
    "            upper.append(cur)\n",
    "            cur = cur.left \n",
    "        lower = []\n",
    "        cur = root \n",
    "        while cur:\n",
    "            lower.append(cur)\n",
    "            cur = cur.right \n",
    "        while upper and upper[-1].val < target:\n",
    "            move_upper()\n",
    "        while lower and lower[-1].val >= target:\n",
    "            move_lower()\n",
    "        res = []\n",
    "        for _ in range(k):\n",
    "            l = lower[-1].val if lower else - float('inf')\n",
    "            u = upper[-1].val if upper else float('inf')\n",
    "            if u - target <= target - l:\n",
    "                res.append(u)\n",
    "                move_upper()\n",
    "            else:\n",
    "                res.append(l)\n",
    "                move_lower()\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def closestKValues(self, root: Optional[TreeNode], target: float, k: int) -> List[int]:\n",
    "        # 中序遍历得到有序节点列表\n",
    "        def inorder(node):\n",
    "            if not node: return []\n",
    "            return inorder(node.left) + [node.val] + inorder(node.right)\n",
    "        # 找到最接近的元素的索引\n",
    "        def closest_index(arr, target):\n",
    "            left, right = 0, len(arr) - 1\n",
    "            while left < right:\n",
    "                mid = (left + right) // 2\n",
    "                if arr[mid] == target:\n",
    "                    return mid\n",
    "                elif arr[mid] < target:\n",
    "                    left = mid + 1\n",
    "                else:\n",
    "                    right = mid\n",
    "            return left\n",
    "        # 找到k个最接近的元素\n",
    "        nodes = inorder(root)      # 中序遍历得到有序节点列表\n",
    "        closest_idx = closest_index(nodes,target)   # 找到最接近的元素的索引\n",
    "        left, right = closest_idx - 1, closest_idx  # 初始化左右指针\n",
    "        result = []    # 存放最接近的k个元素\n",
    "        for _ in range(k):\n",
    "            if left >= 0 and right < len(nodes):\n",
    "                if abs(nodes[left] - target) < abs(nodes[right] - target):\n",
    "                    result.append(nodes[left])  # 将左侧的节点加入结果\n",
    "                    left -= 1   # 左指针向左移动\n",
    "                else:\n",
    "                    result.append(nodes[right])  # 将右侧的节点加入结果\n",
    "                    right += 1  # 右指针向右移动\n",
    "            elif left >= 0:\n",
    "                result.append(nodes[left])  # 将左侧的节点加入结果\n",
    "                left -= 1   # 左指针向左移动\n",
    "            elif right < len(nodes):\n",
    "                result.append(nodes[right])  # 将右侧的节点加入结果\n",
    "                right += 1  # 右指针向右移动\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def closestKValues(self, root: TreeNode, target: float, k: int) -> List[int]:\n",
    "        if not root:\n",
    "            retrun \n",
    "        # 解法2:中序遍历（左-根-右），遍历过程中判断是否已经在res并且比较第0个值与target\n",
    "        res = []\n",
    "        self.inorder(root, target, k, res)\n",
    "        return res\n",
    "        \n",
    "    def inorder(self, root, target, k, res):\n",
    "        if not root:\n",
    "            return\n",
    "        self.inorder(root.left, target, k, res)\n",
    "        if k > len(res):\n",
    "            res.append(root.val)\n",
    "        elif abs(res[0] - target) > abs(root.val - target):\n",
    "            res.pop(0)\n",
    "            res.append(root.val)\n",
    "        else:\n",
    "            return\n",
    "        self.inorder(root.right, target, k, res)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def closestKValues(self, root: Optional[TreeNode], target: float, k: int) -> List[int]:\n",
    "        q = collections.deque()\n",
    "\n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return\n",
    "            dfs(node.left)\n",
    "            if len(q) < k:\n",
    "                q.append(node.val)\n",
    "            elif abs(q[0] - target) > abs(node.val - target):\n",
    "                q.popleft()\n",
    "                q.append(node.val)\n",
    "            else:\n",
    "                return\n",
    "            dfs(node.right)\n",
    "\n",
    "        dfs(root)\n",
    "        return list(q)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def closestKValues(self, root: Optional[TreeNode], target: float, k: int) -> List[int]:\n",
    "        dec,inc = [],[]\n",
    "        while root:\n",
    "            if root.val<=target: \n",
    "                dec.append(root)\n",
    "                root = root.right\n",
    "            else: \n",
    "                inc.append(root)\n",
    "                root = root.left\n",
    "        \n",
    "        res = []\n",
    "        while k:\n",
    "            k-=1\n",
    "            ldiff = target-dec[-1].val if dec else 10**9+7\n",
    "            rdiff = inc[-1].val-target if inc else 10**9+7\n",
    "            if ldiff<=rdiff:\n",
    "                root = dec.pop()\n",
    "                res.append(root.val)\n",
    "                root = root.left\n",
    "                while root:\n",
    "                    dec.append(root)\n",
    "                    root = root.right\n",
    "            else:\n",
    "                root = inc.pop()\n",
    "                res.append(root.val)\n",
    "                root = root.right\n",
    "                while root:\n",
    "                    inc.append(root)\n",
    "                    root = root.left\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def closestKValues(self, root: TreeNode, target: float, k: int) -> List[int]:\n",
    "        return karr_of_tree(root, target, k)\n",
    "\n",
    "\n",
    "def karr_of_tree(tree, target, k):\n",
    "    if not tree: return []\n",
    "    if k <= 0: return []\n",
    "    if target < tree.val:\n",
    "        left = karr_of_tree(tree.left, target, k)\n",
    "        lt_ct = bisect.bisect_left(left, target)\n",
    "        gt_ct = len(left) - lt_ct\n",
    "        # 再去右边取k-1-gt_ct个(tree.val算一个,所以减1)\n",
    "        right = bottomK_of_tree(tree.right, k-1-gt_ct)\n",
    "        cands = [*left, tree.val, *right]\n",
    "    else:\n",
    "        right = karr_of_tree(tree.right, target, k)\n",
    "        lt_ct = bisect.bisect_right(right, target)\n",
    "        # 再去左边取k-1-lt_ct个(tree.val算一个,所以减1)\n",
    "        left = topK_of_tree(tree.left, k-1-lt_ct)\n",
    "        cands = [*left, tree.val, *right]\n",
    "    i, j = 0, len(cands)-1\n",
    "    while j - i > k-1:\n",
    "        if abs(target-cands[i]) > abs(target-cands[j]):\n",
    "            i += 1\n",
    "        else:\n",
    "            j -= 1\n",
    "    return cands[i:j+1]\n",
    "        \n",
    "\n",
    "\n",
    "def topK_of_tree(tree, K):\n",
    "    if K <= 0: return []\n",
    "    if not tree: return []\n",
    "    right = topK_of_tree(tree.right, K)\n",
    "    if len(right) == K:\n",
    "        ans = right\n",
    "    else:\n",
    "        ans = [*topK_of_tree(tree.left, K-len(right)-1), tree.val, *right]\n",
    "    return ans\n",
    "\n",
    "\n",
    "def bottomK_of_tree(tree, K):\n",
    "    if K <= 0: return []\n",
    "    if not tree: return []\n",
    "    left = bottomK_of_tree(tree.left, K)\n",
    "    if len(left) == K:\n",
    "        ans = left\n",
    "    else:\n",
    "        ans = [*left, tree.val, *bottomK_of_tree(tree.right, K-len(left)-1)]\n",
    "    return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def closestKValues(self, root: TreeNode, target: float, k: int) -> List[int]:\n",
    "        ans = []\n",
    "        arr = []\n",
    "        def dfs(root):# 中序遍历\n",
    "            if root is None:\n",
    "                return\n",
    "            dfs(root.left)\n",
    "            arr.append(root.val)\n",
    "            dfs(root.right)\n",
    "        dfs(root)\n",
    "        right = bisect_left(arr, target)\n",
    "        left = right - 1\n",
    "        for i in range(k):# 双指针\n",
    "            if left>=0 and right < len(arr):\n",
    "                if abs(arr[left] - target) <= abs(arr[right] - target):\n",
    "                    ans.append(arr[left])\n",
    "                    left -= 1\n",
    "                else:\n",
    "                    ans.append(arr[right])\n",
    "                    right += 1\n",
    "            elif left>=0:\n",
    "                ans.append(arr[left])\n",
    "                left -= 1\n",
    "            else:\n",
    "                ans.append(arr[right])\n",
    "                right += 1\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def closestKValues(self, root: Optional[TreeNode], target: float, k: int) -> List[int]:\n",
    "        \n",
    "        ret = []\n",
    "\n",
    "        def visit(root):\n",
    "            if not root:\n",
    "                return\n",
    "            ret.append(root.val)\n",
    "            visit(root.left)\n",
    "            visit(root.right)\n",
    "        visit(root)\n",
    "        return sorted(ret, key=lambda x: abs(x - target))[:k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def closestKValues(self, root: Optional[TreeNode], target: float, k: int) -> List[int]:\n",
    "        ans = []\n",
    "        arr = []\n",
    "\n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return\n",
    "            dfs(root.left)\n",
    "            arr.append(root.val)\n",
    "            dfs(root.right)\n",
    "\n",
    "        dfs(root)\n",
    "        r = bisect_left(arr,target)\n",
    "        l = r - 1\n",
    "        for i in range(k):\n",
    "            if l >= 0 and r < len(arr):\n",
    "                if abs(arr[l] - target) <= abs(arr[r] - target):\n",
    "                    ans.append(arr[l])\n",
    "                    l -= 1\n",
    "                else:\n",
    "                    ans.append(arr[r])\n",
    "                    r += 1\n",
    "            elif l >= 0:\n",
    "                ans.append(arr[l])\n",
    "                l -= 1\n",
    "            else:\n",
    "                ans.append(arr[r])\n",
    "                r += 1\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def closestKValues(self, root: Optional[TreeNode], target: float, k: int) -> List[int]:\n",
    "        h=[]\n",
    "        def dfs(x):\n",
    "            if x:\n",
    "                cur=x.val\n",
    "                d=abs(cur-target)\n",
    "                if len(h)<k:\n",
    "                    heapq.heappush(h,(-d,cur))\n",
    "                else:\n",
    "                    if d<-h[0][0]:\n",
    "                        heapq.heapreplace(h,(-d,cur))\n",
    "                dfs(x.left)\n",
    "                dfs(x.right)\n",
    "        dfs(root)\n",
    "        return [v[1] for v in h]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "\n",
    "def merge(r1, r2, target, k):\n",
    "    tmp = [(abs(n - target), n) for n in r1 + r2]\n",
    "    tmp.sort()\n",
    "    return [n[1] for n in tmp[:k]]\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def closestKValues(self, root: Optional[TreeNode], target: float, k: int) -> List[int]:\n",
    "        results = []\n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return \n",
    "\n",
    "            dfs(root.left)\n",
    "            dfs(root.right)\n",
    "            \n",
    "            item = (-abs(root.val - target), root.val)\n",
    "            if len(results) < k:\n",
    "                heapq.heappush(results, item)\n",
    "            else:\n",
    "                heapq.heappushpop(results, item)\n",
    "        dfs(root)\n",
    "        return [r[1] for r in results]\n",
    "        \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def closestKValues(self, root: Optional[TreeNode], target: float, k: int) -> List[int]:\n",
    "        queue = collections.deque()\n",
    "\n",
    "        def traverse(node: Optional[TreeNode]):\n",
    "            if not node: return\n",
    "            traverse(node.left)\n",
    "            if len(queue) < k:\n",
    "                queue.append(node.val)\n",
    "            else:\n",
    "                if abs(node.val - target) < abs(target - queue[0]):\n",
    "                    queue.popleft()\n",
    "                    queue.append(node.val)\n",
    "                else:\n",
    "                    return\n",
    "            traverse(node.right)\n",
    "        traverse(root)\n",
    "        return list(queue)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def closestKValues(self, root: Optional[TreeNode], target: float, k: int) -> List[int]:\n",
    "        q = collections.deque()\n",
    "\n",
    "        def inorder(root):\n",
    "            if root is None:\n",
    "                return\n",
    "            inorder(root.left)\n",
    "            if len(q) < k:\n",
    "                q.append(root.val)\n",
    "            else:\n",
    "                if root.val < target or abs(q[0] - target) > root.val - target:\n",
    "                    q.popleft()\n",
    "                    q.append(root.val)\n",
    "            inorder(root.right)\n",
    "        \n",
    "        inorder(root)\n",
    "        \n",
    "        return list(q)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def closestKValues(self, root: Optional[TreeNode], target: float, k: int) -> List[int]:\n",
    "        nums = []\n",
    "        def inOrder(node):\n",
    "            if node is None:\n",
    "                return\n",
    "            inOrder(node.left)\n",
    "            nums.append(node.val)\n",
    "            inOrder(node.right)\n",
    "        inOrder(root)\n",
    "        # print(nums)\n",
    "        nums.sort(key = lambda x:abs(x - target))\n",
    "        return nums[:k]\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def closestKValues(self, root: Optional[TreeNode], target: float, k: int) -> List[int]:\n",
    "        heap = []\n",
    "\n",
    "        def inorder(node):\n",
    "            if not node: return\n",
    "\n",
    "            inorder(node.left)\n",
    "\n",
    "            heapq.heappush(heap, (-abs(node.val - target), node.val))\n",
    "            if len(heap) > k:\n",
    "                heapq.heappop(heap)\n",
    "\n",
    "            inorder(node.right)\n",
    "        \n",
    "        inorder(root)\n",
    "        return [val for _,val in heap]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "\n",
    "from heapq import *\n",
    "class Solution:\n",
    "    def closestKValues(self, root: Optional[TreeNode], target: float, k: int) -> List[int]:\n",
    "        hq = [(-float('inf'), 0)]\n",
    "        def findVal(root,target,k):\n",
    "            if not root:\n",
    "                return\n",
    "            diff = -abs(root.val-target)\n",
    "            if len(hq) < k:\n",
    "                heappush(hq, (diff, root.val))\n",
    "            else:\n",
    "                v, _ = hq[0]\n",
    "                if diff > v:\n",
    "                    heappop(hq)\n",
    "                    heappush(hq, (diff, root.val))\n",
    "            findVal(root.left, target, k)\n",
    "            findVal(root.right, target, k)\n",
    "        \n",
    "        findVal(root,target,k)\n",
    "        ans =[]\n",
    "        for _, val in hq:\n",
    "            ans.append(val)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def closestKValues(self, root: Optional[TreeNode], target: float, k: int) -> List[int]:\n",
    "        import heapq\n",
    "        buffer = []\n",
    "        \n",
    "        def bt(node):\n",
    "            if not node:\n",
    "                return\n",
    "            if len(buffer) < k:\n",
    "                buffer.append((-abs(node.val - target), node.val))\n",
    "                if len(buffer) == k:\n",
    "                    heapq.heapify(buffer)\n",
    "            else:\n",
    "                if buffer[0][0] < -abs(node.val - target):\n",
    "                    heapq.heappop(buffer)\n",
    "                    heapq.heappush(buffer, (-abs(node.val - target), node.val))\n",
    "        \n",
    "            bt(node.left)\n",
    "            bt(node.right)\n",
    "        \n",
    "        bt(root)\n",
    "        ret_list = [item[1] for item in buffer]\n",
    "        return ret_list\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def closestKValues(self, root: Optional[TreeNode], target: float, k: int) -> List[int]:\n",
    "        min_value = 2.1e9\n",
    "        topk = []\n",
    "        stack = []\n",
    "        node = root\n",
    "        last_val = None\n",
    "        while len(stack) > 0 or node is not None:\n",
    "            if node is not None:\n",
    "                stack.append(node)\n",
    "                node = node.left\n",
    "            else:\n",
    "                node = stack.pop()\n",
    "                # print(node.val)\n",
    "                if len(topk) < k:\n",
    "                    heapq.heappush(topk, (-abs(node.val - target), node.val))\n",
    "                else:\n",
    "                    if abs(topk[0][0]) > abs(target - node.val):\n",
    "                        heapq.heappop(topk)\n",
    "                        heapq.heappush(topk, (-abs(node.val - target), node.val))\n",
    "                    else:\n",
    "                        return [i[1] for i in topk]\n",
    "                node = node.right\n",
    "        return [i[1] for i in topk]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "\n",
    "def add(results, root, target, k):\n",
    "    item = (-abs(root.val - target), root.val)\n",
    "    if len(results) < k:\n",
    "        heapq.heappush(results, item)\n",
    "    else:\n",
    "        heapq.heappushpop(results, item)\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def closestKValues(self, root: Optional[TreeNode], target: float, k: int) -> List[int]:\n",
    "        results = []\n",
    "        def inner(root):\n",
    "            if not root:\n",
    "                return \n",
    "\n",
    "            inner(root.left)\n",
    "            add(results, root, target, k)\n",
    "            inner(root.right)\n",
    "\n",
    "        inner(root)\n",
    "        return [r[1] for r in results]\n",
    "        \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def closestKValues(self, root: Optional[TreeNode], target: float, k: int) -> List[int]:\n",
    "\n",
    "        def inorder(root):\n",
    "            if not root:\n",
    "                return []\n",
    "            \n",
    "            \n",
    "            close_diff = [] # heap\n",
    "            stack = []\n",
    "            cur = root\n",
    "\n",
    "            while cur or stack:\n",
    "                if cur:\n",
    "                    stack.append(cur)\n",
    "                    cur = cur.left\n",
    "                else:\n",
    "                    cur = stack.pop()\n",
    "                    cur_val = cur.val\n",
    "                    diff = abs(cur_val - target)\n",
    "                    if len(close_diff) < k:\n",
    "                        heapq.heappush(close_diff, (-diff, cur_val))\n",
    "                    else:\n",
    "                        if -diff > close_diff[0][0]:\n",
    "                            while len(close_diff) >= k:\n",
    "                                heapq.heappop(close_diff)\n",
    "                            heapq.heappush(close_diff, (-diff, cur_val))\n",
    "                    cur = cur.right\n",
    "                    #print(close_diff)\n",
    "            \n",
    "            return close_diff\n",
    "        \n",
    "        anw = inorder(root)\n",
    "        return [i[1] for i in anw]\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "\n",
    "def add(results, root, target, k):\n",
    "    item = (-abs(root.val - target), root.val)\n",
    "    if len(results) < k:\n",
    "        heapq.heappush(results, item)\n",
    "    else:\n",
    "        heapq.heappushpop(results, item)\n",
    "\n",
    "def root_min(root):\n",
    "    if not root:\n",
    "        return None\n",
    "    while root.left:\n",
    "        root = root.left\n",
    "    return root.val\n",
    "\n",
    "def root_max(root):\n",
    "    if not root:\n",
    "        return None\n",
    "    while root.right:\n",
    "        root = root.right\n",
    "    return root.val\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def closestKValues(self, root: Optional[TreeNode], target: float, k: int) -> List[int]:\n",
    "        results = []\n",
    "        def inner(root):\n",
    "            if not root:\n",
    "                return \n",
    "\n",
    "            inner(root.left)\n",
    "            add(results, root, target, k)\n",
    "            inner(root.right)\n",
    "\n",
    "\n",
    "        inner(root)\n",
    "        return [r[1] for r in results]\n",
    "        \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def dfs(self, node: TreeNode, target: float, k: int) -> None:\n",
    "        if node == None:\n",
    "            return \n",
    "        diff = abs(node.val - target)\n",
    "        if len(self.max_heap) < k:              #最大堆可以容纳k个\n",
    "            heapq.heappush(self.max_heap, (-diff, node.val))        #node会报错 Python会说TreeNode无法比较\n",
    "        else:\n",
    "            if diff < self.max_heap[0][0] * (-1): #让差距更小的进堆\n",
    "                heapq.heappop(self.max_heap)\n",
    "                heapq.heappush(self.max_heap, (-diff, node.val))\n",
    "        self.dfs(node.left, target, k)          #递归左子\n",
    "        self.dfs(node.right, target, k)         #递归右子\n",
    "\n",
    "    def closestKValues(self, root: TreeNode, target: float, k: int) -> List[int]:\n",
    "        self.max_heap = []\n",
    "        self.dfs(root, target, k)\n",
    "        res = []\n",
    "        for diff, node_val in self.max_heap:\n",
    "            res.append(node_val)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "\n",
    "def add(results, root, target, k):\n",
    "    item = (-abs(root.val - target), root.val)\n",
    "    if len(results) < k:\n",
    "        heapq.heappush(results, item)\n",
    "    else:\n",
    "        heapq.heappushpop(results, item)\n",
    "\n",
    "def root_min(root):\n",
    "    if not root:\n",
    "        return None\n",
    "    while root.left:\n",
    "        root = root.left\n",
    "    return root.val\n",
    "\n",
    "def root_max(root):\n",
    "    if not root:\n",
    "        return None\n",
    "    while root.right:\n",
    "        root = root.right\n",
    "    return root.val\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def closestKValues(self, root: Optional[TreeNode], target: float, k: int) -> List[int]:\n",
    "        results = []\n",
    "        def inner(root):\n",
    "            if not root:\n",
    "                return \n",
    "\n",
    "            inner(root.left)\n",
    "            add(results, root, target, k)\n",
    "            inner(root.right)\n",
    "\n",
    "\n",
    "        inner(root)\n",
    "        return [r[1] for r in results]\n",
    "        \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "\n",
    "def add(results, root, target, k):\n",
    "    item = (-abs(root.val - target), root.val)\n",
    "    if len(results) < k:\n",
    "        heapq.heappush(results, item)\n",
    "    else:\n",
    "        heapq.heappushpop(results, item)\n",
    "\n",
    "def root_min(root):\n",
    "    if not root:\n",
    "        return None\n",
    "    while root.left:\n",
    "        root = root.left\n",
    "    return root.val\n",
    "\n",
    "def root_max(root):\n",
    "    if not root:\n",
    "        return None\n",
    "    while root.right:\n",
    "        root = root.right\n",
    "    return root.val\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def closestKValues(self, root: Optional[TreeNode], target: float, k: int) -> List[int]:\n",
    "        results = []\n",
    "        def inner(root):\n",
    "            if not root:\n",
    "                return \n",
    "\n",
    "            if target <= root.val:\n",
    "                inner(root.left)\n",
    "                add(results, root, target, k)\n",
    "                if not root.right:\n",
    "                    return\n",
    "                if len(results) < k:\n",
    "                    inner(root.right)\n",
    "                    return\n",
    "                right_min = root_min(root.right)\n",
    "                if abs(target - right_min) <= -results[0][0]:\n",
    "                    inner(root.right)\n",
    "                    return\n",
    "            else:\n",
    "                inner(root.right)\n",
    "                add(results, root, target, k)\n",
    "                if not root.left:\n",
    "                    return\n",
    "                if len(results) < k:\n",
    "                    inner(root.left)\n",
    "                    return\n",
    "                left_max = root_max(root.left)\n",
    "                if abs(target - left_max) <= -results[0][0]:\n",
    "                    inner(root.left)\n",
    "                    return\n",
    "\n",
    "\n",
    "        inner(root)\n",
    "        return [r[1] for r in results]\n",
    "        \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "\n",
    "def add(results, root, target, k):\n",
    "    item = (-abs(root.val - target), root.val)\n",
    "    if len(results) < k:\n",
    "        heapq.heappush(results, item)\n",
    "    else:\n",
    "        heapq.heappushpop(results, item)\n",
    "\n",
    "def root_min(root):\n",
    "    if not root:\n",
    "        return None\n",
    "    while root.left:\n",
    "        root = root.left\n",
    "    return root.val\n",
    "\n",
    "def root_max(root):\n",
    "    if not root:\n",
    "        return None\n",
    "    while root.right:\n",
    "        root = root.right\n",
    "    return root.val\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def closestKValues(self, root: Optional[TreeNode], target: float, k: int) -> List[int]:\n",
    "        results = []\n",
    "        def inner(root):\n",
    "            if not root:\n",
    "                return \n",
    "\n",
    "            if target <= root.val:\n",
    "                inner(root.left)\n",
    "                add(results, root, target, k)\n",
    "                if not root.right:\n",
    "                    return\n",
    "                if len(results) < k:\n",
    "                    inner(root.right)\n",
    "                    return\n",
    "                right_min = root_min(root.right)\n",
    "                if abs(target - right_min) <= -results[0][0]:\n",
    "                    inner(root.right)\n",
    "                    return\n",
    "            else:\n",
    "                inner(root.right)\n",
    "                add(results, root, target, k)\n",
    "                if not root.left:\n",
    "                    return\n",
    "                if len(results) < k:\n",
    "                    inner(root.left)\n",
    "                    return\n",
    "                left_max = root_max(root.left)\n",
    "                if abs(target - left_max) <= -results[0][0]:\n",
    "                    inner(root.left)\n",
    "                    return\n",
    "\n",
    "\n",
    "        inner(root)\n",
    "        return [r[1] for r in results]\n",
    "        \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def closestKValues(self, root: Optional[TreeNode], target: float, k: int) -> List[int]:\n",
    "        def dfs(root):\n",
    "            if not root: return\n",
    "            dfs(root.left)\n",
    "            res.append(root.val)\n",
    "            dfs(root.right)\n",
    "        res=[]\n",
    "        dfs(root)\n",
    "\n",
    "        res2=[]\n",
    "        for i in res:\n",
    "            res2.append(-abs(target-i))\n",
    "\n",
    "        pq=list()\n",
    "        for i,num in enumerate(res2):\n",
    "            heapq.heappush(pq,(num,i))\n",
    "            if len(pq)>k:\n",
    "                heapq.heappop(pq)\n",
    "        ans=[]\n",
    "        for m in pq:\n",
    "            ans.append(res[m[1]])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def closestKValues(self, root: Optional[TreeNode], target: float, k: int) -> List[int]:\n",
    "        from heapq import heappush, heappop\n",
    "        myHeap = []\n",
    "        \n",
    "        def traverse(root: Optional[TreeNode]):\n",
    "            nonlocal myHeap\n",
    "            if not root:\n",
    "                return\n",
    "            heappush(myHeap, (abs(root.val-target+0.001), root))\n",
    "            traverse(root.left)\n",
    "            traverse(root.right)\n",
    "        traverse(root)\n",
    "        res = []\n",
    "        for i in range(k):\n",
    "            res.append(heappop(myHeap)[1].val)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def closestKValues(self, root: Optional[TreeNode], target: float, k: int) -> List[int]:\n",
    "        pq = []\n",
    "        def dfs(node):\n",
    "            if node:\n",
    "                heappush(pq, (abs(node.val - target), node.val))\n",
    "                dfs(node.left)\n",
    "                dfs(node.right)\n",
    "        dfs(root)\n",
    "\n",
    "        res = []\n",
    "        for i in range(k):\n",
    "            res.append(heappop(pq)[1])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def closestKValues(self, root: Optional[TreeNode], target: float, k: int) -> List[int]:\n",
    "        def dfs(root):\n",
    "            if not root: return\n",
    "            dfs(root.left)\n",
    "            res.append(root.val)\n",
    "            dfs(root.right)\n",
    "        res=[]\n",
    "        dfs(root)\n",
    "\n",
    "        res2=[]\n",
    "        for i in res:\n",
    "            res2.append(-abs(target-i))\n",
    "\n",
    "        pq=list()\n",
    "        for i,num in enumerate(res2):\n",
    "            heapq.heappush(pq,(num,i))\n",
    "            if len(pq)>k:\n",
    "                heapq.heappop(pq)\n",
    "        ans=[]\n",
    "        for m in pq:\n",
    "            ans.append(res[m[1]])\n",
    "        return ans\n",
    "\n",
    "\n",
    "# class Solution:\n",
    "#     def closestKValues(self, root: TreeNode, target: float, k: int) -> List[int]:\n",
    "#         ans = []\n",
    "#         arr = []\n",
    "#         def dfs(root):# 中序遍历\n",
    "#             if root is None:\n",
    "#                 return\n",
    "#             dfs(root.left)\n",
    "#             arr.append(root.val)\n",
    "#             dfs(root.right)\n",
    "#         dfs(root)\n",
    "#         right = bisect_left(arr, target)\n",
    "#         left = right - 1\n",
    "#         for i in range(k):# 双指针\n",
    "#             if left>=0 and right < len(arr):\n",
    "#                 if abs(arr[left] - target) <= abs(arr[right] - target):\n",
    "#                     ans.append(arr[left])\n",
    "#                     left -= 1\n",
    "#                 else:\n",
    "#                     ans.append(arr[right])\n",
    "#                     right += 1\n",
    "#             elif left>=0:\n",
    "#                 ans.append(arr[left])\n",
    "#                 left -= 1\n",
    "#             else:\n",
    "#                 ans.append(arr[right])\n",
    "#                 right += 1\n",
    "#         return ans\n",
    "# #### 双指针也可以记录最小k，为什么"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
